package 回溯;

import sun.applet.Main;

import java.util.Arrays;

public class _面试题_08_07_无重复字符串的排列组合 {

    private Integer index = 0;

    public String[] permutation(String S) {
        int len = S.length();
        if (S == null || len == 0) return new String[]{};
        int num = 1;
        int count = 1;
        while (num <= len) {
            count *= num;
            num++;
        }
        String[] res = new String[count];
        char[] arr = S.toCharArray();
        boolean[] used = new boolean[arr.length];
        backtrack(res, arr, 0, used, new StringBuilder());
        return res;
    }

    private void backtrack(String[] res, char[] arr, int level, boolean[] used, StringBuilder lujing) {
        if (level == arr.length) {
            res[index] = lujing.toString();
            index = index + 1;
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            lujing.append(arr[i]);
            backtrack(res,arr,level + 1,used,lujing);
            used[i] = false;
            lujing.deleteCharAt(lujing.length() - 1);
        }
    }

    public static void main(String[] args) {
        _面试题_08_07_无重复字符串的排列组合 o = new _面试题_08_07_无重复字符串的排列组合();
        String[] qwes = o.permutation("qwe");
        System.out.println(Arrays.toString(qwes));
    }
}
